
import java.util.*;

/*
    102. 二叉树的层序遍历
    二叉树的层序遍历思路为：
    维护一个队列LinkedList，先将头节点压入队列
    1）	弹出一个节点，打印（处理）；
    2）	将该节点的左节点，右节点依次压入队列；
    3）	重复上述两步
    在这个过程中，一般需要记录所在层和节点所在层，用一个map来记录节点所在层
 */

public class LevelOrder {

    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            List<List<Integer>> ans = new ArrayList<>();
            return ans;
        }
        ArrayList<List<Integer>> ans = new ArrayList<>();
        ArrayList<Integer> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        HashMap<TreeNode, Integer> map = new HashMap<>();
        queue.add(root);
        int curLevel = 1;
        int curLevelNodes = 0;
        int max = Integer.MIN_VALUE;
        map.put(root, 1);
        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            int curNodeLevel = map.get(poll);
            if (curLevel == curNodeLevel) {
                list.add(poll.val);
                curLevelNodes++;
            } else {
                ans.add(list);
                list = new ArrayList<Integer>();
                list.add(poll.val);
                max = Math.max(max, curLevelNodes);
                curLevelNodes = 1;
                curLevel++;
            }

            if (poll.left != null) {
                map.put(poll.left, curLevel + 1);
                queue.add(poll.left);
            }
            if (poll.right != null) {
                map.put(poll.right, curLevel + 1);
                queue.add(poll.right);
            }
        }
        ans.add(list);
        return ans;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
